package Leetcode;

import java.util.ArrayList;
import java.util.List;

public class problem442 {
    public static List<Integer> findDuplicates(int[] nums) {

        List<Integer> aList = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return aList;
        }


        for(int i = 0; i < nums.length;i++){
            while(nums[i] != i + 1 && nums[i] != 0){
                if(nums[i] == nums[nums[i]-1]){
                    aList.add(nums[i]);
                    nums[i] = 0;
                    break;
                }else{
                    swap(nums,i,nums[i]-1);
                }
            }
        }

        return aList;
    }

    public static void swap(int[] arr , int i , int j){
        // arr[i] = arr[i] ^ arr[j];
        // arr[j] = arr[i] ^ arr[j];
        // arr[i] = arr[i] ^ arr[j];
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4,3,2,7,8,2,3,1};
        findDuplicates(arr);
    }
}
